#ifndef LEFTISTHEAP_H
#define LEFTISTHEAP_H
#include <iomanip>
#include <iostream>
using namespace std;

template<class T>
class LeftistNode
{
public:
    T m_key;
    int m_nNpl; // 零路经长度(Null Path Length)
    LeftistNode *m_left;
    LeftistNode *m_right;

    LeftistNode(T val, LeftistNode *l, LeftistNode *r) :
        m_key(val), m_nNpl(0), m_left(l), m_right(r){}
};

template <class T>
class LeftistHeap
{
private:
    LeftistNode<T> *m_Root;    // 根结点

public:
    LeftistHeap();
    ~LeftistHeap();

    // 前序遍历"左倾堆"
    void preOrder();
    // 中序遍历"左倾堆"
    void inOrder();
    // 后序遍历"左倾堆"
    void postOrder();

    // 将other的左倾堆合并到this中。
    void merge(LeftistHeap<T>* other);
    // 将结点(key为节点键值)插入到左倾堆中
    void insert(T key);
    // 删除结点(key为节点键值)
    void remove();

    // 销毁左倾堆
    void destroy();

    // 打印左倾堆
    void print();
private:

    // 前序遍历"左倾堆"
    void preOrder(LeftistNode<T>* heap) const;
    // 中序遍历"左倾堆"
    void inOrder(LeftistNode<T>* heap) const;
    // 后序遍历"左倾堆"
    void postOrder(LeftistNode<T>* heap) const;

    // 交换节点x和节点y
    void swapNode(LeftistNode<T> *&x, LeftistNode<T> *&y);
    // 合并"左倾堆x"和"左倾堆y"
    LeftistNode<T>* merge(LeftistNode<T>* &x, LeftistNode<T>* &y);
    // 将结点(z)插入到左倾堆(heap)中
    LeftistNode<T>* insert(LeftistNode<T>* &heap, T key);
    // 删除左倾堆(heap)中的结点(z)，并返回被删除的结点
    LeftistNode<T>* remove(LeftistNode<T>* &heap);

    // 销毁左倾堆
    void destroy(LeftistNode<T>* &heap);

    // 打印左倾堆
    void print(LeftistNode<T>* heap, T key, int direction);
};

template<class T>
LeftistHeap<T>::LeftistHeap() : m_Root(nullptr)
{

}

template<class T>
LeftistHeap<T>::~LeftistHeap()
{
    destroy(m_Root);
}

template<class T>
void LeftistHeap<T>::preOrder(LeftistNode<T> *heap) const
{
    if(heap != nullptr)
    {
        cout << heap->m_key << " ";
        preOrder(heap->m_left);
        preOrder(heap->m_right);
    }
}

template<class T>
void LeftistHeap<T>::preOrder()
{
    preOrder(m_Root);
}

template<class T>
void LeftistHeap<T>::inOrder(LeftistNode<T> *heap) const
{
    if(heap != nullptr)
    {
        preOrder(heap->m_left);
        cout << heap->m_key << " ";
        preOrder(heap->m_right);
    }
}

template<class T>
void LeftistHeap<T>::inOrder()
{
    inOrder(m_Root);
}

template<class T>
void LeftistHeap<T>::postOrder(LeftistNode<T> *heap) const
{
    if(heap != nullptr)
    {
        preOrder(heap->m_left);
        preOrder(heap->m_right);
        cout << heap->m_key << " ";
    }
}

template<class T>
void LeftistHeap<T>::postOrder()
{
    postOrder(m_Root);
}

template<class T>
void LeftistHeap<T>::swapNode(LeftistNode<T> *&x, LeftistNode<T> *&y)
{
    auto tmp = x;
    x = y;
    y = tmp;
}

template<class T>
LeftistNode<T> *LeftistHeap<T>::merge(LeftistNode<T> *&x, LeftistNode<T> *&y)
{
    if( x == nullptr )
        return y;
    if( y == nullptr )
        return x;

    // 合并x和y时，将x作为合并后的树的根
    // 这里的操作是保证: x的key < y的key
    if( x->m_key > y->m_key)
        swapNode(x, y);

    x->m_right = merge(x->m_right, y);

    // 如果"x的左孩子为空" 或者 "x的左孩子的npl<右孩子的npl"
    // 则，交换x和y
    if(x->m_left == nullptr || x->m_left->m_nNpl < x->m_right->m_nNpl)
    {
        swapNode(x->m_left, x->m_right);
    }

    // 设置合并后的新树(x)的npl
    if(x->m_right == nullptr || x->m_left == nullptr)
        x->m_nNpl = 0;
    else
        x->m_nNpl = (x->m_left->m_nNpl > x->m_right->m_nNpl) ? (x->m_right->m_nNpl + 1) : (x->m_left->m_nNpl + 1);

    return x;
}


template<class T>
void LeftistHeap<T>::merge(LeftistHeap<T> *other)
{
    m_Root = merge(m_Root, other->m_Root);
}


// 将结点插入到左倾堆中，并返回根节点
template<class T>
LeftistNode<T> *LeftistHeap<T>::insert(LeftistNode<T> *&heap, T key)
{
    auto node = new LeftistNode<T>(key, nullptr, nullptr);
    if( node == nullptr)
    {
        cout << "ERROR: create node failed!" << endl;
        return heap;
    }

    return merge(m_Root, node);
}

template<class T>
void LeftistHeap<T>::insert(T key)
{
    m_Root = insert(m_Root, key);
}

template<class T>
LeftistNode<T> *LeftistHeap<T>::remove(LeftistNode<T> *&heap)
{
    if(heap == nullptr)
        return nullptr;

    auto l = heap->m_left;
    auto r = heap->m_right;

    delete heap;
    return merge(l, r);
}

template<class T>
void LeftistHeap<T>::remove()
{
    m_Root = remove(m_Root);
}


template<class T>
void LeftistHeap<T>::destroy(LeftistNode<T> *& heap)
{
    if( heap == nullptr)
        return ;

    if(heap->m_left != nullptr)
        destroy(heap->m_left);
    if(heap->m_right != nullptr)
        destroy(heap->m_right);

    delete heap;
}


template<class T>
void LeftistHeap<T>::destroy()
{
    destroy(m_Root);
}

template<class T>
void LeftistHeap<T>::print(LeftistNode<T> *heap, T key, int direction)
{
    if(heap != nullptr)
    {
        if(direction == 0)
            cout << setw(2) << heap->m_key << "(" << heap->m_nNpl << ") is root" << endl;
        else
            cout << setw(2) << heap->m_key << "(" << heap->m_nNpl << ") is " << setw(2) << key << "'s "  << setw(12) << (direction==1?"right child" : "left child") << endl;

        print(heap->m_left, heap->m_key, -1);
        print(heap->m_right, heap->m_key, 1);
    }
}

template<class T>
void LeftistHeap<T>::print()
{
    if(m_Root != nullptr)
        print(m_Root, m_Root->m_key, 0);
}


#endif // LEFTISTHEAP_H
